{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split a Circular Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: splitCircularLinkedList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #拆分循环链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现给定一个由正整数组成的 <strong>循环链表</strong> <code>list</code> ，你的任务是将其拆分为 2 个 <strong>循环链表</strong> ，使得第一个链表包含 <code>list</code> <strong>前半部分&nbsp;</strong>的节点（即 <code>ceil(list.length / 2)</code> 个节点），顺序与 list 中的顺序相同，而第二个链表包含 <code>list</code> 中 <strong>剩余</strong> 的节点，顺序也与 <code>list</code> 中的顺序相同。</p>\n",
    "\n",
    "<p>返回一个长度为 2 的数组，其中第一个元素是表示 <strong>前半部分</strong> 链表的<strong> 循环链表</strong> ，第二个元素是表示 <strong>后半部分</strong> 链表的 <strong>循环链表</strong> 。</p>\n",
    "\n",
    "<p><strong>循环链表</strong> 是一个普通的链表，唯一的区别是最后一个节点的下一个节点是头节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,5,7]\n",
    "<b>输出：</b>[[1,5],[7]]\n",
    "<b>解释：</b>初始链表有3个节点，因此前半部分是前两个元素，剩下的 1 个节点在后半部分。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,6,1,5]\n",
    "<b>输出：</b>[[2,6],[1,5]]\n",
    "<b>解释：</b>初始链表有4个节点，因此前半部分是前两个元素，剩下的 2 个节点在后半部分。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>list</code> 中的节点数范围为 <code>[2, 105]</code></li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>LastNode.next = FirstNode</code> ，其中 <code>LastNode</code> 是链表的最后一个节点，<code>FirstNode</code> 是第一个节点。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-a-circular-linked-list](https://leetcode.cn/problems/split-a-circular-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-a-circular-linked-list](https://leetcode.cn/problems/split-a-circular-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,5,7]', '[2,6,1,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def splitCircularLinkedList(self, list: Optional[ListNode]) -> List[Optional[ListNode]]:\n",
    "        p1,p2,lst,f = list,list,list,1\n",
    "        while p2.next != list:\n",
    "            lst,p1 = p1,p1.next\n",
    "            if p2.next.next != list:\n",
    "               p2 = p2.next.next\n",
    "               f += 2\n",
    "            else:\n",
    "                p2 = p2.next\n",
    "                f += 1\n",
    "        mid = p1 if f & 1 else lst\n",
    "        q = mid.next\n",
    "        mid.next = list\n",
    "        p2.next = q\n",
    "        return [list,q]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitCircularLinkedList(self, head: Optional[ListNode]) -> List[Optional[ListNode]]:\n",
    "        fast = slow = head\n",
    "        while fast.next != head and fast.next.next != head:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next      \n",
    "        \n",
    "        t = slow.next\n",
    "        if fast.next == head: fast.next = t\n",
    "        if fast.next.next == head: fast.next.next = t\n",
    "        slow.next = head\n",
    "        return [head, t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitCircularLinkedList(self, list: Optional[ListNode]) -> List[Optional[ListNode]]:\n",
    "        slow, fast, pre_slow, fast_steps = list, list, list, 1\n",
    "        while fast.next != list:\n",
    "            pre_slow, slow = slow, slow.next \n",
    "            if fast.next.next != list:\n",
    "                fast = fast.next.next\n",
    "                fast_steps += 2\n",
    "            else:\n",
    "                fast = fast.next\n",
    "                fast_steps += 1\n",
    "        left_tail = slow if fast_steps % 2 == 1 else pre_slow\n",
    "        right_head = left_tail.next\n",
    "        left_tail.next = list\n",
    "        fast.next = right_head\n",
    "        \n",
    "        return [list, right_head]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitCircularLinkedList(self, list: Optional[ListNode]) -> List[Optional[ListNode]]:\n",
    "        p1,p2,lst,f = list,list,list,1\n",
    "        while p2.next != list:\n",
    "            lst,p1 = p1,p1.next\n",
    "            if p2.next.next != list:\n",
    "               p2 = p2.next.next\n",
    "               f += 2\n",
    "            else:\n",
    "                p2 = p2.next\n",
    "                f += 1\n",
    "        mid = p1 if f & 1 else lst\n",
    "        q = mid.next\n",
    "        mid.next = list\n",
    "        p2.next = q\n",
    "        return [list,q]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitCircularLinkedList(self, l: Optional[ListNode]) -> List[Optional[ListNode]]:\n",
    "      res,s=l,l\n",
    "      f=l.next.next\n",
    "      cur=l.next\n",
    "      while f!=res and f.next!=res:\n",
    "        cur=f.next\n",
    "        f=f.next.next\n",
    "        s=s.next\n",
    "      if f==res:\n",
    "        ls=s.next\n",
    "        s.next=res\n",
    "        cur.next=ls\n",
    "        return [res,ls]\n",
    "      ls=s.next.next\n",
    "      s.next.next=res\n",
    "      f.next=ls\n",
    "      return [res,ls]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitCircularLinkedList(self, list: Optional[ListNode]) -> List[Optional[ListNode]]:\n",
    "        slow=f=list\n",
    "        while f.next != list and f.next.next != list:\n",
    "            slow = slow.next\n",
    "            f = f.next.next\n",
    "\n",
    "        if f.next != list:\n",
    "            f = f.next\n",
    "        \n",
    "        f.next = slow.next\n",
    "        slow.next =list   \n",
    "        return [list,f.next]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def splitCircularLinkedList(self, head):\n",
    "        p1, p2 = head, head \n",
    "        while p2.next != head and p2.next.next != head:\n",
    "            p1 = p1.next \n",
    "            p2 = p2.next.next \n",
    "        if p2.next != head:\n",
    "            p2 = p2.next\n",
    "        second = p1.next \n",
    "        p1.next = head \n",
    "        p2.next = second    \n",
    "        return [head, second]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def splitCircularLinkedList(self, list: Optional[ListNode]) -> List[Optional[ListNode]]:\n",
    "        p1,p2,lst,f = list,list,list,1\n",
    "        while p2.next != list:\n",
    "            lst,p1 = p1,p1.next\n",
    "            if p2.next.next != list:\n",
    "               p2 = p2.next.next\n",
    "               f += 2\n",
    "            else:\n",
    "                p2 = p2.next\n",
    "                f += 1\n",
    "        mid = p1 if f & 1 else lst\n",
    "        q = mid.next\n",
    "        mid.next = list\n",
    "        p2.next = q\n",
    "        return [list,q] \n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
